In the k-edge-connected spanning subgraph problem we are given a graph (V, E)and costs for each edge, and want to find a minimum-cost subset F of E suchthat (V, F) is k-edge-connected. We show there is a constant eps > 0 so thatfor all k > 1, finding a (1 + eps)-approximation for k-ECSS is NP-hard,establishing a gap between the unit-cost and general-cost versions. Next, weconsider the multi-subgraph cousin of k-ECSS, in which we purchase amulti-subset F of E, with unlimited parallel copies available at the same costas the original edge. We conjecture that a (1 + Theta(1/k))-approximationalgorithm exists, and we describe an approach based on graph decompositionsapplied to its natural linear programming (LP) relaxation. The LP isessentially equivalent to the Held-Karp LP for TSP and the undirected LP forSteiner tree. We give a family of extreme points for the LP which are morecomplex than those previously known.
展开▼
